In digital data communications systems, it is common for data packets transmitted over a communications channel to be corrupted by errors, e.g., when communicating in hostile environments. Wireless radio communications are often conducted in an especially hostile environment. The radio channel is subjected to a barrage of corrupting factors including noise, rapidly changing communications channel characteristics, multi-path fading, and time dispersion which may cause intersymbol interference, and interference from adjacent channel communications.
There are numerous techniques that may be employed by a receiver to detect such errors. One example of an error detection technique is the well-known Cyclic Redundancy Check (CRC). Other techniques use more advanced types of block codes or convolutional codes to accomplish both error detection and error correction. For both error detection and error correction, channel coding is applied which adds redundancy to the data. When information is received over a communications channel, the received data is decoded using the redundancy to detect if the data has been corrupted by errors. The more redundancy built into a unit of data, the more likely errors can be accurately detected, and in some instances, corrected.
In many communication systems, including wireless communications, it is desirable to have a reliable data delivery service that guarantees delivery of data units sent from one machine to another without duplication of data or data loss. Most such reliable data delivery protocols use a fundamental retransmission technique where the receiver of the data responds to the sender of the data with acknowledgements and/or negative acknowledgements This technique is commonly known as Automatic Repeat reQuest (ARQ) transaction processing. Coded data packets are transmitted from a sender to a receiver over a communications channel. Using the error detection bits (the redundancy) included in the coded data packet, each received data packet is processed by the receiver to determine if tile data packet was received correctly or corrupted by errors. If the packet was correctly received, the receiver transmits an acknowledgement (ACK) signal back to the sender. In the most simple form of ARQ, sometimes called Stop-and-Wait (S&W) ARQ, the sender of the data stores each sent packet and waits for an acknowledgement of this packet before sending the next packet. When the ACK is received, the sender discards the stored packet and sends the next packet. An example of a Stop-and-Wait ARQ process is shown in FIG. 1. Vertical distance down the figure represents increasing time, and diagonal lines across the middle represent network data transmissions including acknowledgements.
FIG. 2 uses the same format as FIG. 1 to show what happens when a data packet is lost during transmission from sender to receiver. The sender starts a timer after transmitting the packet. If no acknowledgement is received when the timer expires, the sender assumes the packet was lost or corrupted, and retransmits it. The dotted lines show the time that would be taken by the transmission of a packet and its acknowledgement if the packet was not lost or corrupted. If the receiver detects errors in the packet, it may also send an explicit negative acknowledgement (NACK) to the sender. When the NACK is received, the sender can retransmit the packet without waiting for the timer to expire. In addition, if the ACK or NACK is lost on the link from the receiver to the sender, the timer will also expire, and the sender will retransmit the packet.
Stop-and-Wait ARQ decreases throughput because the sender must delay sending a new packet until it receives an acknowledgement for the previous packet. To avoid this problem, a sliding window form of acknowledgement and retransmission may be employed. With a predetermined window of size W, the sender may transmit up to W consecutive packets before an acknowledgement is received. If the sender does not receive an ACK signal for a specific packet within a predetermined time window, or if the sender receives a NACK signal for a specific packet, the sender retransmits either this data packet (selective repeat ARQ) or this packet and all subsequently transmitted packets (goback-N ARQ). In the example shown in FIGS. 3(a) and 3(b), the window is eight packets in length, and it slides so that packet nine (9) can be sent when an acknowledgement is received for packet one (1).
Because the sliding window ARQ protocol offers the possibility to keep the network saturated with packets, it can achieve substantially higher throughput than a simple Stop-and-Wait protocol. Another example of three packets transmitted using a sliding window ARQ protocol is shown in FIG. 4. The main point illustrated is that the sender can transmit all packets in the window without waiting for an acknowledgement.
Sequence numbers may be assigned to each transmitted data packet.
Sequence numbers are used in the ARQ protocol to identify lost packets and to identify the reception of multiple copies of the same packet. The receiver typically includes the sequence numbers in the acknowledgements, so that acknowledgements can be correctly associated with the corresponding buffered packets. Unfortunately, adding and processing sequence numbers complicates the ARQ protocol implementation.
One simple way of implementing a retransmission scheme is disclosed by David Chase in an article entitled “Code Combining —A Maximum-Likelihood Decoding Approach for Combining an Arbitrary Number of Noisy Packets,” IEEE Transactions on Communications, May 1985, pages 385-391. In this scheme, two Stop-and-Wait ARQ schemes run in parallel and access the channel in alternating time slots as shown in FIG. 5. Each queue keeps track of only one outstanding packet. The odd queue transmits one packet and waits for a positive acknowledgement before moving on to the next packet in the queue. While the receiver processes the received packet from the odd queue, the even queue transmits a packet to the receiver, and so on. The use of these two parallel queues eliminates the significant drawback of the single-queue, Stop-and-Wait ARQ—low throughput—while keeping the simplicity of the Stop-and-Wait protocol.
For the dual queue Stop-and-Wait ARQ protocol to operate properly, however, the receiver must be able to decode and acknowledge a received packet during the time slot during which the other queue is transmitting a packet. It may be difficult to complete this decoding and acknowledgement within the available time when data is transmitted at high speed. For example, high speed data transmitted in a downlink direction from a radio network to a wireless user equipment terminal in cellular radio communications systems may be problematic if the user equipment has only limited processing capabilities to perform the necessary decoding. Time slots may be fairly short, e.g., for scheduling reasons, on the order of just a few milliseconds. During this relatively to short time, the receiver must decode and process a data packet, which in the case of high data rates, may contain several thousands of bits. If the receiver does not completely process such a data packet and transmit an acknowledgement within this short time frame, the transmitter schedules a retransmission of that entire data packet, even if the packet could be correctly decoded. Such unnecessary retransmission of data packets seriously degrades throughput because the radio channel is occupied with retransmission of already correctly decoded data packets.
One possibility to increase the amount of time available for decoding and processing data packets at the receiver is to employ more than two parallel queues, i.e., to allow more than two outstanding packets at the same time. However, using parallel queues increases buffering requirements at both the transmitter and the receiver because each outstanding packet requires its own buffer. Buffering requirements are even more of a concern if “soft” information needs to be buffered at the receiver, as is the case if so-called incremental redundancy is used for the retransmissions. In case of incremental redundancy, the receiver combines multiple retransmissions of the same packet (i.e., combining of “soft information”) before decoding. The use of soft information requires substantially more memory as compared to “hard” information. Moreover, having multiple queues does not reduce the overall data processing speed requirements (millions of instructions per second (MIPS)) in the receiver, even though parallel processing can be advantageous.
Accordingly, it is an object of the present invention to provide a flexible ARQ scheme that permits trading off a desired performance with one or more communication resources required to achieve the desired performance. For example, such a scheme should be able to provide in one instance, higher performance in terms of higher data throughput at a higher resource cost, while in another instance also provide lower performance at a significantly reduced resource cost. The present invention provides such a flexible ARQ scheme.
A communications channel is set up between a transmitter and a receiver. A value is selected for a first parameter of a reliable data packet delivery procedure (RDPDP) for data packets transmitted over the communications channel. The first RDPDP parameter value is selected in accordance with a trade-off between a desired performance or goal, e.g., a specific throughput of data packets transmitted over the communications channel, and one or more resources required to support the desired performance or goal. An example of the first RDPDP parameter is a number of outstanding data packets that must be acknowledged by the receiver before more packets can be sent to the receiver. Another RDPDP parameter example is delay. Such a delay could be an acknowledgement delay denoting a time period between the transmission of a data packet and its acknowledgement. Alternatively, the delay could be a retransmission delay denoting the time period between a transmission and a retransmission (in case of no acknowledgement).
In a preferred, non-limiting example embodiment, first and second parameter values are selected for the desired trade-off Accordingly, a specific number of outstanding data packets and a retransmission delay can be selected to achieve a desired performance, e.g., a desired throughput of data packets, at a particular resource cost.
The value(s) of the first and/or second RDPDP parameters may be determined so that a communication resource is efficiently used in supporting the data packet acknowledgement procedure. Such a communication resource might include one or more of the following: a data processing speed requirement to support the acknowledgement of sent data packets, a buffering requirement to support the acknowledgement of sent data packets, and a power requirement to support the acknowledgement of sent data packets. The value(s) of the first parameter (and the second parameter) may be determined when the packet data communication is established or after the packet data communication is established. Indeed, a parameter value may be modified if some aspect of the packet data communication changes from when the packet data communication was originally established, e.g., a change in service, a change in the configuration or condition of the receiver and/or transmitter. etc.
A smaller number of outstanding packets may be selected, along with a larger delay, in order to reduce buffering requirements and required data processing speed in the receiver. A larger number of outstanding packets may be selected along with a smaller delay to increase the throughput for the packet data communication. A larger number of outstanding packets may be selected along with a larger delay to obtain a higher throughput with a long processing time, but at the cost of larger memory buffers and a higher delay. Because of the flexibility provided by the present invention, a communications device may set its own performance objectives for a particular connection based upon one or more performance requirements or communication resources.